
#include <assert.h>
#include "dosbox.h"
#include "mem.h"
#include "cpu.h"
#include "bios.h"
#include "regs.h"
#include "cpu.h"
#include "callback.h"
#include "inout.h"
#include "pic.h"
#include "hardware.h"
#include "pci_bus.h"
#include "joystick.h"
#include "mouse.h"
#include "callback.h"
#include "setup.h"
#include "serialport.h"
#include "mapper.h"
#include "vga.h"
#include "regionalloctracking.h"
#include "parport.h"
#include <time.h>
#include <sys/timeb.h>

/* Really, Microsoft, Really?? You're the only compiler I know that doesn't understand ssize_t! */
#if defined(_MSC_VER)
#include <basetsd.h>
typedef SSIZE_T ssize_t;
#endif

RegionAllocTracking::Block::Block() : start(0), end(0), free(true) {
}

RegionAllocTracking::RegionAllocTracking() : _min(0), _max(~((Bitu)0)), topDownAlloc(false) {
}

Bitu RegionAllocTracking::getMemory(Bitu bytes,const char *who,Bitu alignment,Bitu must_be_at) {
	if (bytes == 0u) return alloc_failed;
	if (alignment > 1u && must_be_at != 0u) return alloc_failed; /* avoid nonsense! */
	if (who == NULL) who = "";
	if (alist.empty()) E_Exit("getMemory called when '%s' allocation list not initialized",name.c_str());

	/* alignment must be power of 2 */
	if (alignment == 0u)
		alignment = 1u;
	else if ((alignment & (alignment-1u)) != 0u)
		E_Exit("getMemory called with non-power of 2 alignment value %u on '%s'",(int)alignment,name.c_str());

	{
		/* allocate downward from the top */
		size_t si = topDownAlloc ? (alist.size() - 1u) : 0u;
		while ((ssize_t)si >= 0) {
			Block &blk = alist[si];
			Bitu base;

			if (!blk.free || (blk.end+1u-blk.start) < bytes) {
				if (topDownAlloc) si--;
				else si++;
				continue;
			}

			/* if must_be_at != 0 the caller wants a block at a very specific location */
			if (must_be_at != 0) {
				/* well, is there room to fit the forced block? if it starts before
				 * this block or the forced block would end past the block then, no. */
				if (must_be_at < blk.start || (must_be_at+bytes-1u) > blk.end) {
					if (topDownAlloc) si--;
					else si++;
					continue;
				}

				base = must_be_at;
				if (base == blk.start && (base+bytes-1u) == blk.end) { /* easy case: perfect match */
					blk.free = false;
					blk.who = who;
				}
				else if (base == blk.start) { /* need to split */
					Block newblk = blk; /* this becomes the new block we insert */
					blk.start = base+bytes;
					newblk.end = base+bytes-1u;
					newblk.free = false;
					newblk.who = who;
					alist.insert(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si,newblk);
				}
				else if ((base+bytes-1) == blk.end) { /* need to split */
					Block newblk = blk; /* this becomes the new block we insert */
					blk.end = base-1;
					newblk.start = base;
					newblk.free = false;
					newblk.who = who;
					alist.insert(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si+1u,newblk);
				}
				else { /* complex split */
					Block newblk = blk,newblk2 = blk; /* this becomes the new block we insert */
					Bitu orig_end = blk.end;
					blk.end = base-1u;
					newblk.start = base+bytes;
					newblk.end = orig_end;
					alist.insert(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si+1u,newblk);
					newblk2.start = base;
					newblk2.end = base+bytes-1u;
					newblk2.free = false;
					newblk2.who = who;
					alist.insert(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si+1u,newblk2);
				}
			}
			else {
				if (topDownAlloc) {
					base = blk.end + 1u - bytes; /* allocate downward from the top */
					assert(base >= blk.start);
				}
				else {
					base = blk.start; /* allocate upward from the bottom */
					assert(base <= blk.end);
					base += alignment - 1u; /* alignment round up */
				}

				base &= ~(alignment - 1u); /* NTS: alignment == 16 means ~0xF or 0xFFFF0 */
				if (base < blk.start || (base+bytes-1u) > blk.end) { /* if not possible after alignment, then skip */
					if (topDownAlloc) si--;
					else si++;
					continue;
				}

				if (topDownAlloc) {
					/* easy case: base matches start, just take the block! */
					if (base == blk.start) {
						blk.free = false;
						blk.who = who;
						return blk.start;
					}

					/* not-so-easy: need to split the block and claim the upper half */
					RegionAllocTracking::Block newblk = blk; /* this becomes the new block we insert */
					newblk.start = base;
					newblk.free = false;
					newblk.who = who;
					blk.end = base - 1u;

					if (blk.start > blk.end) {
						sanityCheck();
						abort();
					}

					alist.insert(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si+1,newblk);
				}
				else {
					if ((base+bytes-1u) == blk.end) {
						blk.free = false;
						blk.who = who;
						return blk.start;
					}

					/* not-so-easy: need to split the block and claim the lower half */
					RegionAllocTracking::Block newblk = blk; /* this becomes the new block we insert */
					newblk.start = base+bytes;
					blk.free = false;
					blk.who = who;
					blk.end = base+bytes-1u;

					if (blk.start > blk.end) {
						sanityCheck();
						abort();
					}

					alist.insert(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si+1u,newblk);
				}
			}

			LOG(LOG_BIOS,LOG_DEBUG)("getMemory in '%s' (0x%05x bytes,\"%s\",align=%u,mustbe=0x%05x) = 0x%05x",name.c_str(),(int)bytes,who,(int)alignment,(int)must_be_at,(int)base);
			sanityCheck();
			return base;
		}
	}

	LOG(LOG_BIOS,LOG_DEBUG)("getMemory in '%s' (0x%05x bytes,\"%s\",align=%u,mustbe=0x%05x) = FAILED",name.c_str(),(int)bytes,who,(int)alignment,(int)must_be_at);
	sanityCheck();
	return alloc_failed;
}

Bitu RegionAllocTracking::getMinAddress() {
	size_t si = 0;
	Bitu r = _max;

	while (si < alist.size()) {
		Block &blk = alist[si];
		if (blk.free) {
			si++;
			continue;
		}

		r = blk.start;
		break;
	}

	return r;
}

void RegionAllocTracking::initSetRange(Bitu start,Bitu end) {
	Block x;

	assert(start <= end);

	alist.clear();
	_min = start;
	_max = end;

	x.end = _max;
	x.free = true;
	x.start = _min;
	alist.push_back(x);
}

void RegionAllocTracking::logDump() {
	size_t si;

	LOG(LOG_MISC,LOG_DEBUG)("%s dump:",name.c_str());
	for (si=0;si < alist.size();si++) {
		Block &blk = alist[si];
		LOG(LOG_MISC,LOG_DEBUG)("     0x%08x-0x%08x free=%u %s",(int)blk.start,(int)blk.end,blk.free?1:0,blk.who.c_str());
	}
	LOG(LOG_MISC,LOG_DEBUG)("[end dump]");
}

void RegionAllocTracking::sanityCheck() {
	Block *pblk,*blk;
	size_t si;

	if (alist.size() <= 1)
		return;

	pblk = &alist[0];
	for (si=1;si < alist.size();si++) {
		blk = &alist[si];
		if (blk->start != (pblk->end+1) || blk->start > blk->end || blk->start < _min || blk->end > _max) {
			LOG(LOG_MISC,LOG_DEBUG)("RegionAllocTracking sanity check failure in '%s'",name.c_str());
			logDump();
			E_Exit("ROMBIOS sanity check failed");
		}

		pblk = blk;
	}
}

Bitu RegionAllocTracking::freeUnusedMinToLoc(Bitu phys) {
	if (phys <= _min) return _min;
	if ((_max+(Bitu)1) != (Bitu)0 && phys > (_max+1)) phys = _max+1;

	/* scan bottom-up */
	while (alist.size() != 0) {
		RegionAllocTracking::Block &blk = alist[0];
		if (!blk.free) {
			if (phys > blk.start) phys = blk.start;
			break;
		}
		if (phys > blk.end) {
			/* remove entirely */
			alist.erase(alist.begin());
			continue;
		}
		if (phys <= blk.start) break;
		blk.start = phys;
		break;
	}

	assert(phys >= _min);
	assert(_max == (Bitu)0 || phys < _max);
	return phys;
}

void RegionAllocTracking::compactFree() {
	size_t si=0;

	while ((si+1u) < alist.size()) {
		RegionAllocTracking::Block &blk1 = alist[si];
		RegionAllocTracking::Block &blk2 = alist[si+1u];

		if (blk1.free && blk2.free) {
			if ((blk1.end+(Bitu)1u) == blk2.start) {
				blk1.end = blk2.end;
				alist.erase(alist.begin()+(std::vector<RegionAllocTracking::Block>::difference_type)si+1u);
				continue;
			}
		}

		si++;
	}

	sanityCheck();
}

bool RegionAllocTracking::freeMemory(Bitu offset) {
	size_t si=0;

	if (offset < _min || offset > _max)
		return false;

	while (si < alist.size()) {
		RegionAllocTracking::Block &blk = alist[si];

		if (offset >= blk.start && offset <= blk.end) {
			LOG(LOG_BIOS,LOG_DEBUG)("freeMemory in '%s' (address=0x%08lx block='%s' range=0x%08lx-0x%08lx) success",
				name.c_str(),(unsigned long)offset,blk.who.c_str(),(unsigned long)blk.start,(unsigned long)blk.end);

			if (!blk.free) {
				blk.free = true;
				blk.who.clear();
				compactFree();
			}

			return true;
		}

		si++;
	}

	LOG(LOG_BIOS,LOG_DEBUG)("freeMemory in '%s' (address=0x%08lx) FAILED",name.c_str(),(unsigned long)offset);
	return false;
}

